In graphic image processing techniques, a path refers to a vector linked-list consisted of linked straight-line vectors and curve vectors. A path in which the vector linked-list is connected end-to-end is referred to as a closed path. A closed path is generally employed to describe a particular region which can be referred to as a graphics element. For example, if a graphics element needs to be filled in with a color, a closed path which is the boundary of a region to be filled in is used to describe the graphics element. Or, if a graphics element needs to be cut out, a closed path which is the boundary of a region to be cut out is also used to describe the graphics element. However, in prior art, a path is described according to the order of appearance of vectors, without considering positional relations of various vectors in the path. Therefore, self-intersection generally exists in the obtained path. A closed path with self-intersection is not the simplest path for describing a region, because superfluous vector description may exist, i.e. some of the vectors constituting the closed path are not located on the boundary of the region described by the closed path, but located inside the region. A path with self-intersection is referred to as a complex path. FIG. 1 is a schematic diagram of a complex path which consists of five straight-line vectors T0, T1, T2, T3, T4 connected end-to-end. A complex path will cause great inconvenience to path computation on a vector level. Correspondingly, a closed path in which each vector constituting the closed path is located on the boundary of the region described by the closed path is referred to as a simple path, which is the simplest path for defining the region.
In current graphic image processing techniques, a mechanism of rasterization bitmap processing is employed to determine a region described by a complex path. For example, two paths (a first path and a second path) for describing a region to be cut out superimpose each other, and a closed path formed after the superimposition is a complex path. The region to be cut out which is described by the complex path should be the intersection of respective regions described by the two paths, and is determined in the following manner. First of all, algorithms relating to Graphics are used to convert a first path to a black and white bitmap, in which a black point indicates that the point is within the described region and a white point indicates that the point is outside the described region. Similarly, a second path is converted to another black and white bitmap. Then the intersection of the two bitmaps is evaluated, i.e. only when both points in the same position are black points, the point can be determined as a block point, and thereby the region to be cut out is finally determined. Of course, it is also possible to evaluate the union of the two black and white bitmaps according to actual demands and thus finally determine the region to be cut out.
However, in the course of some graphic image processing, it is required that a particular region is still described by vectors, rather than rasterised bitmaps, after processing a complex path. For example, a trap process adopts various graphics elements to describe objects required to display in a PDF file, and it needs to fill a particular color in an intersecting position of two graphics elements to obtain trapping effects. The intersecting position also needs to be provided in a manner of graphics elements in PDF files. Therefore, it is required to perform operations on a vector level on closed paths describing the two graphics elements, to acquire vector description of the intersecting position. Employing algorithms relating to Computational Geometry can perform operations on a vector level on closed paths, on the premise that the closed paths on which operations are performed are simple paths, while a complex path with self-intersection can not be processed. However, during actual graphic image processing, degrees of freedom of a closed path for describing a graphics element are very high and the closed path is usually a complex path. Therefore, there is a pressing need for a solution which can simplify any complex path to a simple path of a region described by the complex path.